package leetCode.function;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

// 线段重叠，统计同时在线人数等问题
public class xianduanchongdie {

	private int process(int[][] arr) {
		int result = 0;
		PriorityQueue<int[]> queue1 = new PriorityQueue<int[]>();
		PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});

		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < arr.length; i++) {
			if (!queue.isEmpty()) {
				while (queue.peek()[1] < arr[i][0]) {
					queue.poll();
				}
			}
			queue.offer(arr[i]);
//			result = Math.max(result, queue.size());
			if(queue.size()>result) {
				result = queue.size();
				queue1 = new PriorityQueue<int[]>(queue);
			}
		}
		int l = 0, r = Integer.MAX_VALUE;
		while(!queue1.isEmpty()) {
			int[] a = queue1.poll();
			l = Math.max(l, a[0]);
			r = Math.min(r, a[1]);
		}
		System.out.println(l+" "+r);
		return result;
	}

	public static void main(String[] args) {
		int[][] arr = new int[][] { { 1, 6 }, { 3, 5 }, { 4, 7 }, { 7, 8 }, { 1, 2 },{4,9},{3,6} };
		System.out.println(new xianduanchongdie().process(arr));
	}
}
